
/**
 * 
 * boss的收入
 * 
 * 题目描述

一个XX产品行销总公司，只有一个boss，其有若干一级分销，一级分销又有若干二级分销，每个分销只有唯一的上级分销。

规定，每个月，下级分销需要将自己的总收入（自己的+下级上交的）每满100元上交15元给自己的上级。 

现给出一组分销的关系，和每个分销的收入，请找出boss并计算出这个boss的收入。

比如：

收入100元，上交15元；
收入199元（99元不够100），上交15元；
收入200元，上交30元。

输入：

分销关系和收入：[[分销id 上级分销id 收入], [分销id 上级分销id 收入], [分销id 上级分销id 收入]]
分销ID范围： 0..65535
收入范围：0..65535，单位元
提示：

输入的数据只存在1个boss，不存在环路
输出：

[boss的ID, 总收入]

输入描述
第一行输入关系的总数量 N
第二行开始，输入关系信息，格式：

分销ID 上级分销ID 收入

比如：

5
1 0 100
2 0 199
3 0 200
4 0 200
5 0 200
输出描述
输出：

boss的ID 总收入

比如：

0 120

用例
输入	5
1 0 100
2 0 199
3 0 200
4 0 200
5 0 200
输出	0 120
说明	
无
 * 
 */

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Map.Entry;

/**
 * 
 * 本题的代理商结构其实就是一个树形结构，树根就是顶级代理商。

因此，本题要求顶级代理商的钱，其实就是一个深搜过程，即每个父级代理商的钱 要从其所有子级商汲取（每100元抽15元）。

本题的难点在于，不知道树根是哪个？即不知道顶级代理商号是多少。

我的解题思路如下：

定义一个income字典，其key是代理商号，val是该代理商赚的钱
定义一个agents集合来记录所有出现过的代理商号
定义一个ch_fa字典，其key是子级代理商，val是父级代理商
定义一个fa_ch字典，其key是父级代理商，val是一个集合，记录key的所有子级代理商
而顶级代理商必然没有父级，因此，我们只要遍历agents，用被遍历到的每一个agent去ch_fa中找，如果找不到，则说明对应的agent就是顶级代理商号root。

找到顶级代理商号root后，根据fa_ch，找到root代理商的所有子代理商chs，然后遍历chs，得到每一个ch的赚的钱，从每个ch赚的钱中100抽15，汲取到root代理商赚的钱中。

当然，每个ch赚的钱，也有来自于ch的子级代理商们，同样按照每100抽15的规则汲取。这是一个递归过程。
 * 
 * 
 * 自底向上（拓扑排序） 替代 递归，避免oom
 * 
 *Map  putIfAbsent 如果key存在不会覆盖   put 如果key存在 会覆盖

 变量 map  income 保存 代理 id 和 金额  父类默认金额 0
变量 map inDegree 保存节点的深度，父

通过 ArrayDeque 保存深度为 0 的节点
遍历ArrayDeque ArrayDeque.pollFirset 拿到
 *  深度为 0 的点，深度为 0 的点就是子节点，通过直接点找到父节点，然后计算父节点的金额
 * 处理完子节点后，父节点深度减1，当父节点深度==0 时，将父节点保存到ArrayDeque队尾，
 * ArrayDeque.addLast
 * 当处理完ArrayDeque最后一个元素就是 boss 节点，此时他的金额也获取到
 * 自下而上的处理方式
 *  
 */

public class boss的收入 {


    //代理和收入的关系字典
    private static Map<Integer, Integer> income = new HashMap<Integer, Integer>();
    //深度
    private static Map<Integer, Integer> inDegree = new HashMap<Integer, Integer>();
    //记录 ch 的后继（父）节点
    private static Map<Integer, Integer> next = new HashMap<Integer, Integer>();

    public static void main(String[] args){

        try{
            
            Scanner scanner = new Scanner(System.in);

            //获取总数量
            int chainCount = scanner.nextInt();

            //以此获取关系
            for(int i=0; i<chainCount; i++){

                //子代理
                int childLevelNo = scanner.nextInt();
                //父代理
                int parentLevelNo = scanner.nextInt();
                //金额
                int amount = scanner.nextInt();

                //记录子代理和收入
                income.put(childLevelNo, amount);
                income.putIfAbsent(parentLevelNo, 0);

                //记录深度
                inDegree.put(parentLevelNo, inDegree.getOrDefault(parentLevelNo, 0)+1);
                inDegree.putIfAbsent(childLevelNo, 0);

                next.put(childLevelNo, parentLevelNo);


            }

            //queue记录入度为0的点
            ArrayDeque<Integer> queue = new ArrayDeque<Integer>();

            for(Entry<Integer, Integer> entry : inDegree.entrySet()){

                if (entry.getValue() == 0) {
                    queue.add(entry.getKey());
                }
    
            }

            // 记录最后被剥离的点, 该点就是顶级节点
            int last = 0;

            while (!queue.isEmpty()) {

                int ch = last = queue.pollFirst();

                if(next.containsKey(ch)){

                    // 找到ch的后继（父）节点
                    int parent = next.get(ch);
                    // ch每100元上交15元给fa
                    income.put(parent, income.get(parent) + income.get(ch) / 100 * 15);
 
                    // ch被剥离，fa入度值减1
                    inDegree.put(parent, inDegree.get(parent) - 1);
 
                    // 如果fa的入度为0, 则加入queue
                    if (inDegree.get(parent) == 0) {
                        queue.addLast(parent);
                    }

                }
                
            }

            System.out.println(last + " " + income.get(last));


        }catch(Exception e){
            e.printStackTrace();
            System.out.println("程序异常"+(null==e ? "" : e.getMessage()));
        }

    }
    
}
